﻿/**************************************************************
 * Copyright gt1987. All rights reserved.
 * 
 * Author: guitao(guitao@eastmoney.com) 
 * Create Date: 2020/9/6 15:54:27
 * Description: NumberAlgorithms
 *          
 * Revision History:
 *      Date         Author               Description
 *              
***************************************************************/

using System;
using System.Collections.Generic;
using System.Linq.Expressions;
using System.Text;
using Xunit;

namespace Algorithm.Samples
{
    public class NumberAlgorithms_Test
    {
        [Fact]
        public void Should_IsPerfectSquare()
        {
            NumberAlgorithms alg = new NumberAlgorithms();
            //Assert.True(alg.IsPerfectSquare(9));
            Assert.True(alg.IsPerfectSquare(2147395600));
        }

        [Fact]
        public void Should_CombinationSum3()
        {
            NumberAlgorithms alg = new NumberAlgorithms();
            //Assert.True(alg.IsPerfectSquare(9));
            //Assert.Equal(new List<IList<int>> { new List<int> { 1, 2, 4 } }, alg.CombinationSum3(3, 7));
            Assert.Equal(new List<IList<int>> { new List<int> { 1, 2, 6 }, new List<int> { 1, 3, 5 }, new List<int> { 2, 3, 4 } }, alg.CombinationSum3(3, 9));
        }
    }
    public class NumberAlgorithms
    {
        /// <summary>
        /// 给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
        /// </summary>
        /// <param name="num"></param>
        /// <returns></returns>
        public bool IsPerfectSquare(int num)
        {
            if (num == 0 || num == 1) return true;
            int left = 1;
            int right = int.MaxValue;
            int seed = 1;

            while ((int.MaxValue / (seed + seed)) >= seed + seed)
            {
                seed += seed;
                int val = seed * seed;
                if (val == num)
                {
                    return true;
                }
                if (val < num)
                {
                    left = seed;
                }
                if (val > num)
                {
                    right = seed;
                    break;
                }
            }

            for (int i = left; i <= right; i++)
            {
                if ((int.MaxValue / i) < i)
                {
                    break;
                }
                int val = i * i;
                if (num == i * i)
                {
                    return true;
                }
                if (num < val)
                {
                    break;
                }
            }
            return false;
        }

        /// <summary>
        /// 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。所有数字都是正整数。解集不能包含重复的组合。
        /// 输入:k = 3, n = 9
        /// 输出: [[1,2,6], [1,3,5], [2,3,4]]
        /// </summary>
        /// <param name="k"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public IList<IList<int>> CombinationSum3(int k, int n)
        {
            int[] array = new int[9];
            for (int i = 1; i <= 9; i++)
            {
                array[i - 1] = i;
            }
            dfs(0, array, 0, n, k);
            return ans;
        }
        private List<IList<int>> ans = new List<IList<int>>();
        private IList<int> currentArray = new List<int>();
        private void dfs(int startIndex, int[] source, int sum, int target, int maxCount)
        {
            if (sum > target) return;

            if (target == sum && currentArray.Count == maxCount)
            {
                List<int> b = new List<int>();
                foreach (var t in currentArray)
                {
                    b.Add(t);
                }
                ans.Add(b);
            }
            if (currentArray.Count == maxCount)
            {
                return;
            }

            for (int i = startIndex; i < source.Length; i++)
            {
                var val = source[i];
                currentArray.Add(val);
                dfs(i + 1, source, sum + val, target, maxCount);
                currentArray.RemoveAt(currentArray.Count - 1);
            }
        }


        public void Expression()
        {
            Expression<Func<int, int>> expr1 = x => x + 1;
            Expression<Func<int, int, int>> expr2 = (x, y) => x + y;

        }
    }
}
